{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Randomness in LC-3\n",
    "\n",
    "## Schrage's method\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Assembled! Use %dis or %dump to examine.\n"
     ]
    }
   ],
   "source": [
    ".ORIG x3000\n",
    ";;; Algorithm for the iteration x <- a x mod m\n",
    ";;; using Schrage's method\n",
    "\n",
    "    JSR Random\n",
    "    ;; look in R1 for a pseudo-random value; call Random again to iterate through them\n",
    "    HALT\n",
    "\n",
    ";;; -----------------------------------------------------\n",
    ";;; Memory X has next random number\n",
    "Random: ST R7,BACK  ; save return location\n",
    "    LD R0, M\n",
    "    LD R1, A\n",
    "    JSR Divide          ; R0 / R1\n",
    "    ;; q = m / a\n",
    "    LD R0, QUOTIENT     ; R0 / R1\n",
    "    ST R0, Q \n",
    "    ;; r = m mod a\n",
    "    LD R0, REMAINDER    ; R0 mod R1\n",
    "    ST R0, R\n",
    "        ;; x / q\n",
    "    LD R0, X\n",
    "    LD R1, Q\n",
    "    JSR Divide          ; R0 / R1\n",
    "    LD R1, QUOTIENT\n",
    "    ST R1, TEMP2\n",
    "    LD R1, REMAINDER    ; x mod q\n",
    "    ST R1, TEMP1\n",
    "    ;; x ←  a ∗  (x mod q) − r ∗  (x / q)\n",
    "    ;;      a * TEMP1 - r * TEMP2\n",
    "    LD R0, A\n",
    "    JSR Multiply        ; R2 <- R0 * R1\n",
    "    ST R2, TEMP1\n",
    "    ;;      a * TEMP1 - r * TEMP2\n",
    "    LD R0, R\n",
    "    LD R1, TEMP2\n",
    "    JSR Multiply        ; R2 <- r * TEMP2\n",
    "    NOT R2,R2           ; -R2\n",
    "    ADD R2,R2,#1\n",
    "    ST R2, TEMP2 \n",
    "    LD R1, TEMP1\n",
    "    ADD R2, R2, R1      ; TEMP1 - TEMP2\n",
    "TEST:  BRzp DONE        ; if x < 0 then\n",
    "    LD R1, M\n",
    "    ADD R2, R2, R1      ; x ←  x + m\n",
    "DONE: ST R2, X\n",
    "    LD R7, BACK         ; Restore return address\n",
    "    RET\n",
    "A: .FILL #7             ;; a , the multiplicative constant is given\n",
    "M: .FILL #32767         ;; m = 2 ˆ 15 − 1, the modulus is given\n",
    "X: .FILL #10            ;; x, the seed is given\n",
    "R: .FILL #0\n",
    "Q: .FILL #0\n",
    "TEMP1: .FILL #0\n",
    "TEMP2: .FILL #0\n",
    "BACK: .FILL #0\n",
    "\n",
    ";;; -----------------------------------------------------\n",
    ";;; R2 <- R0 * R1\n",
    ";;; Also uses R3 to store SIGN\n",
    "Multiply: AND R2,R2,#0\n",
    "  AND R3,R3,#0\n",
    "  ADD R0,R0,#0 \t\t; compare R0\n",
    "  BRn MultNEG1\n",
    "  BR  MultCont\n",
    "MultNEG1: NOT R3,R3 \t\t; flip SIGN\n",
    "  NOT R0,R0\n",
    "  ADD R0,R0,#1\n",
    "MultCONT: ADD R1,R1,#0 \t\t; compare R1\n",
    "  BRn MultNEG2\n",
    "  BR MultInit\n",
    "MultNEG2: NOT R3,R3 \t\t; flip SIGN\n",
    "  NOT R1,R1\n",
    "  ADD R1,R1,#1\n",
    "MultInit: ADD R0,R0,#0  \t; have R0 set the condition codes\n",
    "MultLoop: BRz MultDone\n",
    "  ADD R2,R2,R1\n",
    "  ADD R0,R0,#-1\n",
    "  BR MultLoop\n",
    "MultDone: ADD R0,R3,#0\n",
    "  BRzp MultRet\n",
    "  NOT R2,R2\n",
    "  ADD R2,R2,#1\n",
    "MultRet:  RET\t\t\t; R2 has the sum\n",
    "\n",
    ";;; -----------------------------------------------------\n",
    ";;; R0 / R1\n",
    ";;; Also uses R3 to store SIGN\n",
    ";;;           R4 to store -R1\n",
    ";;;           R5 is QUOTIENT\n",
    ";;;           R6 is REMAINDER\n",
    ";;;           R2 temp\n",
    "Divide:   AND R3,R3,#0\n",
    "  ST R3, QUOTIENT\n",
    "  ST R3, REMAINDER\n",
    "  ADD R0,R0,#0 \t\t; compare R0\n",
    "  BRn DivNEG1\n",
    "  BR  DivCont\n",
    "DivNEG1:  NOT R3,R3 \t\t; flip SIGN\n",
    "  NOT R0,R0\n",
    "  ADD R0,R0,#1\n",
    "DivCONT:  ADD R1,R1,#0 \t\t; compare R1\n",
    "  BRn DivNEG2\n",
    "  BR DivInit\n",
    "DivNEG2:  NOT R3,R3 \t\t; flip SIGN\n",
    "  NOT R1,R1\n",
    "  ADD R1,R1,#1\n",
    "DivInit:  ADD R4,R1,#0\n",
    "  NOT R4,R4\n",
    "  ADD R4,R4,#1\n",
    "DivLoop:  ADD R2,R0,R4  \t; have R2 set the condition codes\n",
    "  BRn DivDone\n",
    "  ADD R0,R0,R4\n",
    "  LD R2,QUOTIENT\n",
    "  ADD R2,R2,#1\n",
    "  ST R2,QUOTIENT\n",
    "  BR DivLoop\n",
    "DivDone:  ADD R3,R3,#0 \t\t; Negative?\n",
    "  BRzp DivRet\n",
    "  LD R2,QUOTIENT \t; Yes, then negate R2\n",
    "  NOT R2,R2\n",
    "  ADD R2,R2,#1\n",
    "  ST R2,QUOTIENT\n",
    "DivRet:\t  ST R0,REMAINDER\n",
    "  RET\t\t\t; R2 has the sum\n",
    "QUOTIENT: .FILL #0\n",
    "REMAINDER: .FILL #0\n",
    ".END"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "============================================================\n",
      "Computation completed\n",
      "============================================================\n",
      "Instructions: 32889\n",
      "Cycles: 230203 (0.115101 milliseconds)\n",
      "\n",
      "============================================================\n",
      "Registers:\n",
      "============================================================\n",
      "PC: x048E\n",
      "N: 0 Z: 0 P: 1 \n",
      "R0: x0000 R1: x0046 R2: x0046 R3: x0000 \n",
      "R4: xEDB7 R5: x0000 R6: x0000 R7: x3002 \n"
     ]
    }
   ],
   "source": [
    "%exe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Calysto LC3",
   "language": "gas",
   "name": "calysto_lc3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "gas",
    "version": 3
   },
   "file_extension": ".asm",
   "mimetype": "text/x-gas",
   "name": "gas"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}